package DP.路径;

import org.junit.Test;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    不能涂色，因为要全部路径
    你看都没有+-tv肯定不能g[i][j]=1;
 */
public class 可以往回走_只要不重复就行_左上道右下_路径总数有几种_62 {
    @Test
    public void test() {
        System.out.println(uniquePaths(3,7));
    }

    int n,m;
    int[][] g;
    public int uniquePaths(int n, int m) {
        this.n=n;this.m=m;
        g = new int[n][m];
        //终点 gan最终答案
        int i=n-1,j=m-1;
        return back(i,j);
    }
    private int back(int i, int j) {
        //起点 gan边界人定
        if(i==0 && j==0){
            return 1;
        }
        //照抄
        int xia = 0;
        if(i-1>=0){
            xia = back(i-1,j);
        }
        int you = 0;
        if(j-1>=0 ){
            you = back(i,j-1);
        }
        return xia+you;
    }

    /* 改写dp */
    public static void main(String[] args) {
        int n=3,m=7;
        int[][] dp = new int[n][m];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                //起点
                if(i==0 && j==0){
                    dp[0][0]=1;
                    continue;
                }
                //照抄 return curRes=L+R
                dp[i][j] = (i-1>=0?dp[i-1][j]:0) + (j-1>=0?dp[i][j-1]:0);
            }
        }
        System.out.println(dp[n-1][m-1]);
    }
}
